Description

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

 

Solution

由于要尽可能少发糖，可以先确定一批可以只发一颗糖的孩子（左右相邻的孩子的rating都不小于他），这样与这些孩子相邻的孩子就可以发两颗糖，依次类推。

题目转化为了拓扑排序，求对于每一个孩子第几批能确定所要发的糖果数量（第一批确定的糖果数量是1，第二批是2，第三批是3…）。

用一个图记录各个节点之间的大小关系，图用邻接矩阵表示，可以定义一个顶点代表一个孩子，一条由a孩子指向b孩子的边代表a孩子的rating比b孩子高。用一个数组记录每个小孩所应发的糖果数量。遍历数组，当发现第i个小孩的糖果数量还没确定时，就根据与他相邻的小孩的情况试图确定第这个小孩的糖果数量，如果与他相邻的小孩的发糖数量还没确定，就根据当前已经确定的小孩的糖果数量和邻接矩阵中的信息，把问题转化为确定与他相邻的小孩的发糖数量。这样就形成一个深度优先搜索。

算法的时间复杂度O(n)，空间复杂度O(n)。

 

Caution

1.当试图确定的是第一个和最后一个小孩的发糖数量时，与他相邻的孩子只有一个，需要特殊处理。

2.当与相邻小孩的rating相等，和比相邻小孩的rating小这两种情况是一样的（相等情况）。

3.当N等于1时，直接返回1。

4.由于所要建立的图的边只涉及到相邻节点之间的边，实际只要使用一个N×2的数组即可实现图的存储，无需N×N的数组。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
struct cmp
{
    bool left, right;
};
class Solution {
public:
    int dp(int i, int N, vector<int>& candy, vector<cmp>& cmp)
    {
        if(i == 0)
        {
            if(cmp[0].right)
            {
                if(candy[1]) return candy[0] = candy[1] + 1;
                else return candy[0] = dp(1, N, candy, cmp) + 1;
            }
        }
        if(i == N - 1)
        {
            if(cmp[N - 1].left)
            {
                if(candy[N - 2]) return candy[N - 1] = candy[N - 2] + 1;
                else return candy[N - 1] = dp(N - 2, N, candy, cmp) + 1;
            }
        }
        int l = 0, r = 0;
        if(cmp[i].left)
        {
            if(candy[i - 1]) l = candy[i - 1] + 1;
            else l = dp(i - 1, N, candy, cmp) + 1;
        }
        if(cmp[i].right)
        {
            if(candy[i + 1]) r = candy[i + 1] + 1;
            else r = dp(i + 1, N, candy, cmp) + 1;
        }
        return candy[i] = max(l, r);
    }
    int candy(vector<int>& ratings)
    {
        if(ratings.size() == 0) return 0;
        if(ratings.size() == 1) return 1;
        int N = ratings.size();
        vector<int> candy(N, 0);
        vector<cmp> compare(N);
        for(int i = 0; i < N; i++)
        {
            compare[i].left = compare[i].right = false;
        }
        if(ratings[0] > ratings[1])
        {
            compare[0].right = true;
        }
        else if(ratings[1] > ratings[0])
        {
            candy[0] = 1;
            compare[1].left = true;
        }
        else
        {
            candy[0] = 1;
        }
        for(int i = 1; i < N - 1; i++)
        {
            if(ratings[i - 1] > ratings[i])
            {
                compare[i - 1].right = true;
            }
            else if(ratings[i] > ratings[i - 1])
            {
                compare[i].left = true;
            }
            if(ratings[i + 1] > ratings[i])
            {
                compare[i + 1].left = true;
            }
            else if(ratings[i] > ratings[i + 1])
            {
                compare[i].right = true;
            }
            if(ratings[i - 1] >= ratings[i] && ratings[i] <= ratings[i + 1])
            {
                candy[i] = 1;
            }
        }
        if(ratings[N - 2] > ratings[N - 1])
        {
            candy[N - 1] = 1;
            compare[N - 2].right = true;
        }
        else if(ratings[N - 2] < ratings[N - 1])
        {
            compare[N - 1].left = true;
        }
        else
        {
            candy[N - 1] = 1;
        }
        for(int i = 0; i < N; i++)
        {
            if(candy[i] == 0) dp(i, N, candy, compare);
        }
        return accumulate(candy.begin(), candy.end(), 0);
    }
};